In such network units as are mentioned above, it is convenient or desirable to subject a packet for examination for conformity with one or more ‘rules’. Such an examination is distinct from an address lookup as is performed in switches or routers. Conformity with a rule requires that a relevant selection of portions of a packet match a prescribed set of values held in a rules store. Rules may be simple, in that they require that a particular flag, such as a header flag in a TCP (Transmission Control Protocol) segment have a particular binary value (e.g. the flag is to be set) but in general are rather more complex and require the matching of a large number of bit selected from the packet. One example of a more complex rule is an ACL (Access Control List) rule, which specifies a network source address, a network destination address, an application port number, a source port number and an identification of the protocol and may specify additional fields.
The finding of a match of a rule may have a variety of consequences. For example, they may be used to exert a security check and to prescribe the discard of a packet if the rule is fulfilled. They may prescribe the copying of a packet In switches and routers, where the packet is subjected to a lookup to obtain a forwarding data (usually in the form of a port bit mask) indicating from which port or ports a packet should be forwarded form the unit, the forwarding data is customarily subjected to ‘post-processing’ wherein the forwarding data may be modified as a result of the actions of various processing engines operating in parallel with the lookup engine. A post-processing engine collates the actions of the various processing engines to develop final forwarding data, often in the form of a final forwarding port bit mask, to a forwarding engine. In this context, a rules engine may develop an action which may override or be supplementary to the forwarding data and may be performed by the post-processing engine. However, this context is given by way of example and is not intended to limit the contexts in which the invention in its broadest scope may be employed.
Content Addressable Memories
Content addressable memories (CAMs) are very convenient for use as a rules engine, particularly for long rules, in a rapid manner. As is well known, a content addressable memory has words representing ‘rules’ stored in the data lines and if there is a match between the content of an input ‘key’ word and the content of a data line, the CAM produces a match-indicating signal that identifies that line. Such a signal may be used on its own or as a pointer to a location in an associated memory that store the action associated with the respective rule.
It is known to mask a CAM selectively, by providing along with the input word a masking word that identifies which ‘columns’ are to be excluded from the comparison between the input word and the stored words. This is equivalent to changing the bits that are to masked into ‘don't care’ bits, which in ordinary ternary CAMs do not affect the matching of the rest of the content of a word. One example of masking for use in a somewhat different context is described in published application US 2003/0028713 A1. That document describes the use of masking of the least significant bits of a network address in a lookup engine to discover the longest match of the most significant bits of a multiplicity of network addresses, and the subsequent removal of the mask to obtain an exact match.
The problem to which the invention is directed is the occupancy of excessive space in an expensive CAM (which has a high consumption of power) when a given rule is relevant to a multiplicity of ports of a network unit An example of such rules is Access Control Lists (ACLs). These rules may differ depending on the port on which the packet ingresses. However, there are cases where the same rule would be applied to packets that ingress on any of a multiplicity of ports. The traditional method of applying a rule to different ports would be to store the rule once for each port to which the rule must be applied. An identifier (such as a portID) would be prepended to each rule to signify that the rule is relevant to that particular port The disadvantage of this system is that rules that are applicable to multiple ports must be stored multiple times, thus using valuable CAM storage. In addition, maintenance of the rule requires accesses to multiple CAM locations, thus using valuable bandwidth.
Network units commonly have 24 or 48 ports; but may have more. Moreover they may be cascaded to form a network entity with a number of ports corresponding substantially to the aggregate of the ports of all the units in the cascade.
Although the above discussion relates to packets and ports, there are analogous problems posed by the application of a multiplicity of rules to a packet which may refer to a multiplicity of network entities such as other network units and it is desired to apply the rule in respect of some of the network entities and not others. One example is in the operation of a cascade or mesh system of network units which are managed as if they were a single unit It may be desirable to apply a rule if packets are received by any one of a sub-group of the units but not if the packets are received by other unit s not in the sub-group.
Furthermore if a rule relating to any data pattern might be applicable to a plurality of entities, such as different possible sources of the data pattern (which could be a set of values in a statistical counter), similar problems occur.